A. Field of the Invention
The present invention relates generally to digital networks, and in particular to apparatus and methods for increasing throughput in a connection carried at least partially over an asynchronous transfer mode (ATM) network.
B. Description of the Prior Art
Data transported over a connection frequently crosses several networks, each having a different protocol. The source and destination nodes may employ one protocol, such as Transport Control Protocol (TCP), and a network linking the nodes travels may employ another, such as ATM.
As networks become congested, net throughput decreases. Constant efforts have been made to increase connection throughput and correspondingly decrease network congestion. Moderate increases in throughput are attributable to new congestion avoidance algorithms serving as part of a protocol used to implement a connection. For example, TCP uses a congestion window algorithm to alter source to destination data transfer, and ATM has a variety of services, such as Available Bit Rate Service (ABR), to optimize throughput over a connection. When TCP is carried over ABR, this is referred to as xe2x80x9cTCP over ABR.xe2x80x9d
Using TCP over ABR increases throughput dramatically. The increased throughput, however, is only realized over ATM networks. Therefore, the advantages are only realized when both source and destination are connected over a pure ATM connection. When a TCP connection is partially carried through an ATM network and partially over a non-ATM network, such as an Ethernet LAN, the non-ATM network can become a bottleneck to the overall connection throughput. This is because the TCP congestion window algorithm does not optimize throughput as much as possible. Therefore, even though TCP over ABR raises throughput on the ATM portion of the connection, increased throughput is not realized over the non-ATM portion of the connection.
FIG. 1 is a block diagram showing a prior art network architecture. Ethernet local area network (LAN) 110 is connected to switch 114 and user 116, and ATM network 112 is connected to switch 114 and user 118. The architecture supports communications between user 116 and user 118.
In a typical connection, several protocols may be used simultaneously for a connection between user 116 and user 118. One common combination of protocols is the combined use of TCP and ATM. TCP is a protocol for transporting a byte stream between pairs of hosts, such as user 116 and user 118. ATM is a high bandwidth transmission technology over which TCP connections can be transferred. A TCP byte stream is packetized according to the ATM protocol, transported over the ATM network, depacketized, and reassembled into the original TCP byte stream at the other end.
FIG. 2 is a block diagram showing a conventional switch which may be used as switch 114 of FIG. 1. Switch 114 receives TCP data from Ethernet LAN 110, packetizes the data into ATM data, and depacketizes ATM data from an ATM network into TCP data. Switch 114 is connected to LAN 110 via Ethernet physical interfaces 210 and 218. Data coming from LAN 110 into switch 114 is transferred from Ethernet physical interface 210 to demux 211. Demux 211 associates TCP connections with ATM connections by demultiplexing the TCP data stream into connection buffers 212. Data is then transferred from connection buffers 212 into segmentation and reassembly processor (SAR) 214. Finally, the data is transferred to ATM network 112 by ATM physical interface 216.
In the opposite direction, data is received from ATM network 112 by ATM physical interface 226. ATM physical interface 226 transfers the data through Resource Management (RM) cell demultiplexer 224 to SAR 222, which in turn transfers the data to buffer system 220. Finally, the data is transferred from buffer system 220 to Ethernet physical interface 218, which transfers the data to Ethernet LAN 110.
RM cell demultiplexer 224 extracts RM cells from the incoming ATM data stream and transfers them to SAR 214. RM cells are used in ATM to transfer information regarding resources on the ATM network. For example, RM cells may be used to transfer congestion information. RM cells also include ATM information that identifies the particular connection the resource information is associated with. In response to congestion information in the RM cells, SAR 214 adjusts its output in accordance with the ABR service used on the ATM connection.
ATM supports four service categories that have a variety of performance levels: Constant Bit Rate (CBR), Variable Bit Rate (VBR), Available Bit Rate (ABR), and Unspecified Bit Rate (UBR).
ABR service in ATM networks is primarily used for the transport of best effort data services. ABR sessions share the network bandwidth left over after serving CBR and VBR traffic. This available bandwidth varies with the requirements of the ongoing CBR/VBR sessions by providing rate based feedback in RM cells to the switches carrying ABR sessions. Because TCP is currently the predominant data transport protocol that applications run on over the Internet, TCP traffic is a likely candidate to be carried over the ABR service category.
Data is transferred over ATM network 112 using virtual connections. A virtual connection receives data to be transferred, packetizes the data, transmits the packets over any available path toward the destination, reassembles the packets into the order in which they were transferred, and finally transmits the original data that is transferred. The ATM protocol manages the virtual connection to ensure that data being transferred is reassembled in the same order it was sent. From the user""s standpoint, the virtual connection appears like a physical connection because data is received in the same order it was sent.
Each virtual connection is routed through the network and includes a forward path (from source to destination) and a backward path (from destination to source). For both bidirectional point-to-point and point-to-multipoint connections, the forward and backward components of a virtual connection use the same connection identifiers, and pass through identical transmission facilities.
A source for the ABR service can submit cells into the network at a variable but controlled or shaped rate. SAR 214 performs this function. The ABR source and destination forms an ABR control loop: the ABR source transmits cells for conveying feedback information towards the destination and the destination returns them towards the source.
The ABR service uses RM cells to provide network congestion information to SAR 214. In particular, SAR 214 reduces or increases cell transmission rates depending on the availability of bandwidth in the network as indicated by the RM cells.
Congestion feedback information is used by switch 114 to respond to changes in the available bandwidth by appropriately modifying submission rates of data being transmitted onto ATM 112. This controls or avoids congestion, and the available bandwidth is used.
For ABR connections, the source creates a connection with a call setup request. During this call setup, the values for a set of ABR-specific parameters are identified. Some values are requested by the source and may be modified by the network (e.g., the lower and upper bounds on the source rate), while other values are directly chosen by the network (e.g., the parameters characterizing the process for dynamically updating rates).
Once the source has received permission, it begins cell transmission. The rate at which an ABR source is allowed to schedule cells for transmission is denoted by the Allowed Cell Rate (ACR). In ABR, ACR is initially set to the Initial Cell Rate (ICR), and is always bounded between the Minimum Cell Rate (MCR) and the Peak Cell Rate (PCR). Transmission of data cells is preceded by the sending of an ABR RM cell. The source rate is controlled by the return- of these RM cells, which are looped back by the destination or by a virtual destination.
An RM cell includes several fields, as is well understood in the art. The source places the rate at which it is allowed to transmit cells (its ACR) in the Current Cell Rate (CCR) field of the RM cell, and the rate at which it wishes to transmit cells (usually the PCR) in the Explicit Rate (ER) field. The RM cell travels forward through the network, thus providing the switches in its path with the information in its content for their use in determining the allocation of bandwidth among ABR connections. Switches also may decide at this time to reduce the value of the explicit rate field ER, or set the Congestion Indication bit CI to 1.
Switches optionally generate a controlled number of RM cells on the backward path, in addition to those originally supplied by the source. Switch-generated RM cells preferably has the Backward Notification (BN) bit set to 1 and either the CI bit or the No Increase (M) bit set to 1.
When the cell arrives at the destination, the destination changes the direction bit in the RM cell and return the RM cell to the source. If the destination is congested and cannot support the rate in the ER field, the destination reduces ER to whatever rate it can support.
As the RM cell travels backward through the network, each switch may examine the cell and determine if it can support the rate ER for this connection. If ER is too high, the switch reduces it to the rate that it can support. No switch should increase the ER, since information from switches previously encountered by the RM cell then would be lost. The switches only modify the ER for those connections for which it is a bottleneck, since this promotes a fair allocation of bandwidth. Also, switches modify the ER content of the RM cells traveling on either their forward or backward journeys, but not on both.
Returning to FIG. 2, when the RM cell arrives back at the source, SAR 214 resets its rate, ACR, based on information carried by RM cells. The ABR service may also provide for numerous other adjustments in the source to destination flow control.
A primary motivation for ABR is economical support of data traffic, where each packet of data is segmented into ATM cells, the loss of any one of which causes the re-transmission of the entire packet by a higher protocol layer. By adjusting transmission rates based on feedback from the network to the traffic source, cell loss is controlled within the network. The ABR service guarantees a particular cell-loss ratio for all traffic offered in proper response to network feedback.
TCP Congestion Control
In addition to the rate-based ABR service provided by ATM networks, service quality is also enhanced by higher layer protocols of the network. TCP provides a windowing mechanism which adapts to changes in the network by changing the flow of a TCP connection. A TCP window, which defines an amount of data which can be sent, changes in proportion to acknowledgments per unit time received from remote sites. If acknowledgments are received slowly, the window decreases and transmission slows down. If acknowledgments are received quickly, the window increases and transmission speeds up.
The TCP window defines the amount of outstanding data a sender can send on a particular connection before it gets an acknowledgment back from the receiver. A sliding window algorithm is often used to control flow for network data transfers. When TCP is used for transferring data over the Internet, a sliding window algorithm is used. The sliding window is implemented as a variable-sized buffer between the application program and the network data flow. For TCP, the buffer is typically in the operating system kernel, such as in user 116, but may be implemented elsewhere in the network.
A primary purpose of the sliding window is congestion control. The network connection, which consists of the hosts at both ends, the routers in between, and the actual connections themselves, will have a bottleneck somewhere that can only handle data so fast. If transmission occurs too fast, a bottleneck will not transmit data fast enough and data will be lost. The TCP window throttles the transmission speed down to a level where congestion and data loss do not occur.
Each TCP connection has a TCP transmitter and a TCP receiver, such as user 116 and user 118, respectively, of FIG. 1. The transmitter dynamically adjusts its window size in response to information received from the TCP receiver. The receiver advertises a maximum window beyond which the transmitter""s window cannot increase. When any packet is lost or damaged, the receiver does not acknowledge that packet, causing the transmitter to retransmit the packet.
Congestion is detected in TCP by detecting packet loss resulting from buffer overflow at an intermediate node, or by detecting delayed packets or acknowledgments (ACKs) caused by congestion that in turn causes TCP timeout. In either case, the window drops to one to reduce the load on the network.
FIG. 3 is a chart showing the fluctuations of a prior art TCP congestion window using a typical TCP sliding window algorithm. The sliding window algorithm is not efficient. The window size hunts around an xe2x80x9coptimumxe2x80x9d window size, but always overshoots. This results in packet loss, followed by a reduction in the window size.
FIG. 3 shows two complete cycles of the transmitter window adapting in three separate phases over time. In the slow start phase (312), the TCP transmitter window increases by 1 every time a packet is acknowledged. Therefore, the window doubles every round trip time. This phase continues growing exponentially until the window reaches a threshold. The congestion avoidance phase (314) follows the slow start phase (312). The window grows more slowly than in the slow start phase. Each time a packet is acknowledged, the window grows by 1/Wt, where Wt is the current window size each round trip time. This phase continues until loss occurs, or the window reaches its maximum possible value.
The third and final phase is the loss recovery phase (316). When loss occurs, if packets succeeding the lost packet successfully reach the receiver, the receiver accepts the out-of-sequence packets, but continues to send ACK packets requesting the first lost packet. Therefore, the transmitter window does not grow. The transmitter window slowly becomes empty, and the transmitter starts a timeout clock. At the end of the timeout, advertised window sized drops to zero, and the threshold window Wtth is set to half the current window size, i.e.       W    t    th    =                    w                  t          -                    2        .  
Then the next slow start phase begins with Wt+=1.
The algorithm is useful because it dynamically alters the sender window size in response to congestion information from the receiver. The window adjustments, however, are so extreme that some bandwidth may be wasted. The window size does not closely follow actual fluctuations in congestion of the network. Notably, when the TCP protocol times out, the severe drop preferably reduces the window well below its optimum size.
TCP Over ABR/ATM
The adaptive window congestion control mechanism of TCP that slows down the source during network congestion interacts beneficially with the rate-based explicit feedback control of ABR service from the point of the application level throughput. In TCP over ABR, ABR service works in conjunction with the flow control of TCP to optimize flow on the network. On a lightly loaded network, data is transmitted at the full speed of the line rate. On the other hand, if the network is heavily loaded, switch 114 receives ABR feedback RM cells that indicate congestion, and slows down data transmission in response.
Bandwidth for each virtual ABR connection must fall between a minimum cell rate and peak cell rate. The network provides information about the bandwidth available to the virtual connection through the ABR feedback mechanisms.
Returning to FIG. 2, TCP packets are converted to ATM cells and forwarded to SAR 214. The segmentation buffer receives rate feedback RM cells from the network and the ATM cells are transmitted by SAR 214 at a rate proportional to the rate feedback.
The throughput of TCP traffic can be increased by up to 40% if it is carried over available bit rate ABR end to end. Most users, however, are not connected to an ATM network, but rather to a non-ATM network, such as an Ethernet LAN, as shown in FIG. 1. Therefore, the user does not realize the benefits of using TCP/ABR.
In TCP over ABR, when the feedback loop has a fixed delay, then the ABR source of a session follows the variations in the bandwidth of the bottleneck link without delay. As a result, there is no loss in the network. The TCP window grows until it reaches the maximum window size.
Once the TCP window size exceeds the optimal window size for the connection the packets are buffered in the source buffer. Consequently, congestion is effectively pushed to the network edge. Because the source buffer is much larger than the maximum window size, the TCP window remains fixed at the maximum window size and congestion control will become purely rate-based. Once the ABR control loop converges, no loss will take place in the network and congestion will be pushed to the network edge. If ABR service was not used, however, TCP increases its window, overshoots the optimum window size, and then reduces the window size due to packet loss.
In TCP over ABR, both ABR feedback and TCP congestion control adjust flow control on the network. In this case, the TCP layer in the source host sends TCP packets into the ATM connection buffers 212 where the TCP packets are converted into ATM cells. At time t, the cells are transmitted at a time dependent rate, which depends on the ABR rate feedback indicated by the RM cells. The bottleneck has a finite buffer and has time dependent service rate. If the buffer is full when a cell arrives, the cell is dropped. On the other hand, if the buffer is not full and the packet is not lost, it gets serviced and reaches the destination after some deterministic delay. The destination ATM layer reassembles the packet and delivers it to the TCP receiver. The TCP receiver responds with an ACK which, after some delay (propagation+processing delay) reaches the source. The TCP source responds by increasing the window size.
In the network architecture shown in FIG. 1, user 116 is connected to LAN 110. LAN 110 serves as the last hop to the workstation on one side, and as the connectivity point to ATM network 112 on the other. Therefore, there is a level of indirection between the user and the ATM network. This is the current state of the technology. Because of this indirection, however, the user does not reap the benefits of the application level throughput optimization offered in TCP over ABR as when only an ATM network is involved.
Therefore, there is a need to extend the benefits realized by TCP over ABR to connections carried over ATM and non-ATM networks.
Apparatus and methods consistent with the present invention relate to increasing network throughput over connections employing two or more protocols. More particularly, apparatus and methods consistent with the present Invention increase throughput over connections employing an Asynchronous Transfer Mode (ATM) protocol network and a non-ATM protocol network.
To achieve the objects and in accordance with the purpose of the invention, as embodied and broadly described herein, the invention comprises a method of receiving first congestion information defined by the first protocol; receiving network resource information, wherein the network resource information is not used to determine the first congestion information; determining second congestion information based on network resource information; and transmitting one of the first and second congestion information.
Additional objects and advantages of the invention will be set forth in part in the description which follows, and in part will be obvious from the description, or may be learned by practice of the invention. The objects and advantages of the invention will be realized and attained by means of the elements and combinations particularly pointed out in the appended claims.
It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory only and are not restrictive of the invention, as claimed.
The accompanying drawings, which are incorporated in and constitute a part of this specification, illustrate an embodiment of the invention, which, together with the description, serve to explain the principles of the invention.